// 给定一个二叉树，返回它的中序 遍历。

// 示例:

// 输入: [1,null,2,3]
//    1
//     \
//      2
//     /
//    3

// 输出: [1,3,2]
// 进阶: 递归算法很简单，你可以通过迭代算法完成吗？


var inorderTraversal = function(root) {
    var result = [],
        stack = [];
    // 左子树先入栈，弹出栈顶元素，压入右子树
    while(stack.length > 0 || root) {
        if(root) {
            stack.push(root);
            root = root.left;
        }else {
            let item = stack.pop();
            result.push(item.val);
            root = item.right;
        }
    }
    
    return result;
};